#include <vector>
#include <iostream>
#include <stack>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode * left;
    TreeNode * right;
    TreeNode() : val(0), left(nullptr), right(nullptr)
    {}
    TreeNode(int val) : val(val), left(nullptr), right(nullptr)
    {}
    TreeNode(int val, TreeNode * left, TreeNode * right) : val(val), left(left), right(right)
    {}
};

class Solution 
{
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int> result;
        stack<TreeNode *> st;
        TreeNode * currendNode = root;
        while (currendNode != nullptr || !st.empty())
        {
            while (currendNode != nullptr)
            {
                st.push(currendNode);
                currendNode = currendNode->left;
            }
            while (!st.empty())
            {
                currendNode = st.top();
                result.push_back(currendNode->val);
                st.pop();
                if(currendNode->right != nullptr)
                {
                    currendNode = currendNode->right;
                    break;
                }
                currendNode = nullptr;
            }
        }
        return result;
    }
};

void printVector(const vector<int>& vec)
{
    cout << "[";
    for (size_t i = 0; i < vec.size(); i++) {
        cout << vec[i];
        if (i < vec.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main()
{
    Solution solution;

    // 测试案例1: 题目示例1 - root = [1,null,2,3]
    TreeNode* test1 = new TreeNode(1);
    test1->right = new TreeNode(2);
    test1->right->left = new TreeNode(3);
    cout << "测试案例1: root = [1,null,2,3]" << endl;
    vector<int> result1 = solution.inorderTraversal(test1);
    cout << "结果: ";
    printVector(result1);
    cout << "预期: [1,3,2]" << endl << endl;

    // 测试案例2: 空树
    TreeNode* test2 = nullptr;
    cout << "测试案例2: root = []" << endl;
    vector<int> result2 = solution.inorderTraversal(test2);
    cout << "结果: ";
    printVector(result2);
    cout << "预期: []" << endl << endl;

    // 测试案例3: 单节点
    TreeNode* test3 = new TreeNode(1);
    cout << "测试案例3: root = [1]" << endl;
    vector<int> result3 = solution.inorderTraversal(test3);
    cout << "结果: ";
    printVector(result3);
    cout << "预期: [1]" << endl << endl;

    // 测试案例4: 完全二叉树
    TreeNode* test4 = new TreeNode(1);
    test4->left = new TreeNode(2);
    test4->right = new TreeNode(3);
    test4->left->left = new TreeNode(4);
    test4->left->right = new TreeNode(5);
    test4->right->left = new TreeNode(6);
    test4->right->right = new TreeNode(7);
    cout << "测试案例4: root = [1,2,3,4,5,6,7]" << endl;
    vector<int> result4 = solution.inorderTraversal(test4);
    cout << "结果: ";
    printVector(result4);
    cout << "预期: [4,2,5,1,6,3,7]" << endl << endl;

    // 测试案例5: 左斜树
    TreeNode* test5 = new TreeNode(1);
    test5->left = new TreeNode(2);
    test5->left->left = new TreeNode(3);
    cout << "测试案例5: 左斜树 [1,2,3,null,null,null,null]" << endl;
    vector<int> result5 = solution.inorderTraversal(test5);
    cout << "结果: ";
    printVector(result5);
    cout << "预期: [3,2,1]" << endl << endl;

    // 测试案例6: 右斜树
    TreeNode* test6 = new TreeNode(1);
    test6->right = new TreeNode(2);
    test6->right->right = new TreeNode(3);
    cout << "测试案例6: 右斜树 [1,null,2,null,3]" << endl;
    vector<int> result6 = solution.inorderTraversal(test6);
    cout << "结果: ";
    printVector(result6);
    cout << "预期: [1,2,3]" << endl << endl;

    return 0;
}
